<?php
require 'UF.php';

class UnionFind implements UF
{
    private $parent = [];
    private $size;
    private $sz = []; // sz[$i] 表示以 $i 为根的集合中的元素个数

    /**
     * 初始化并查集
     * UnionFind constructor.
     * @param int $size
     */
    public function __construct(int $size)
    {

        $this->size = $size;
        for ($i = 0; $i < $size; $i++) {
            $this->parent[$i] = $i;
            $this->sz[$i] = 1;
        }

    }

    /**
     * 返回并查集大小
     * @param int $p
     * @param int $q
     * @return int
     */
    public function getSize(int $p, int $q): int
    {
        return $this->size;
    }

    /**
     * 查找p对应的集合编号
     * @param int $p
     */
    public function findRoot(int $p)
    {
        if ($p < 0 || $p >= $this->size) {
            echo "404";
            exit;
        }
        while ($p != $this->parent[$p]) {
            $p = $this->parent[$p];
        }
        return $p;
    }

    /**
     * 判断两个元素是否属于同一个集合
     * @param int $p
     * @param int $q
     * @return bool
     */
    public function isConnected(int $p, int $q): bool
    {
        return $this->findRoot($p) == $this->findRoot($q);
    }

    /**
     * 合并两个元素
     * @param int $p
     * @param int $q
     */
    public function unionElements(int $p, int $q): void
    {
        $pRoot = $this->findRoot($p);
        $qRoot = $this->findRoot($q);
        if ($pRoot != $qRoot) {
            if ($this->sz[$pRoot] < $this->sz[$qRoot]) { //比较两个合并元素根节点的元素个数
                $this->parent[$pRoot] = $qRoot;
                $this->sz[$qRoot] += $this->sz[$pRoot];
            } else {
                $this->parent[$qRoot] = $pRoot;
                $this->sz[$pRoot] += $this->sz[$qRoot];
            }
        }
    }
}